package com.note.feng.leetcode.algorithms.easy;

import java.util.Arrays;

public class EightyEight {

    /**
     * 88 合并两个有序数组
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     *
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     *
     * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
     *
     * 示例 1：
     *
     * 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
     * 输出：[1,2,2,3,5,6]
     * 解释：需要合并 [1,2,3] 和 [2,5,6] 。
     * 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
     * 示例 2：
     *
     * 输入：nums1 = [1], m = 1, nums2 = [], n = 0
     * 输出：[1]
     * 解释：需要合并 [1] 和 [] 。
     * 合并结果是 [1] 。
     * 示例 3：
     *
     * 输入：nums1 = [0], m = 0, nums2 = [1], n = 1
     * 输出：[1]
     * 解释：需要合并的数组是 [] 和 [1] 。
     * 合并结果是 [1] 。
     * 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
     *
     * 提示：
     *
     * nums1.length == m + n
     * nums2.length == n
     * 0 <= m, n <= 200
     * 1 <= m + n <= 200
     * -109 <= nums1[i], nums2[j] <= 109
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/merge-sorted-array
     */
    /**
     * 解法一：
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(n == 0){
            return ;
        }
        for (int i = 0; i < n; i ++){
            int num = nums2[i];
            for(int j = 0; j < m; j ++){
                System.out.println(j + "," + nums1[j] + "," + num);
                if(nums1[j] > num){
                    int k = nums1[j];
                    nums1[j] = num;
                    num = k;
                    break;
                }
            }
            nums1[m ++] = num;
            System.out.println(Arrays.toString(nums1));
//            System.out.println(left);
        }
    }

    /**
     * 解法二:
     * 倒序遍历，两个数组，每次取出较大的数，移动到nums1的最后一个位置上，直到nums2数组遍历完成；
     * 中间会出现如下几种情况：
     * 1、nums1[m-1] > nums2[n-1]
     * 2、nums1[m-1] <= nums2[n-1]
     * 第一种情况：需要交换nums,m-1和index两个下标处的值；同时m--
     * 第二种情况：直接不nums2[n-1]赋值给nums1[index],同时n--
     * 边界判定：
     * 1、如果n == 0,说明nums2已经遍历完成，所有元素都赋值到了nums1中，两个数组合并完成，结束遍历
     * 2、如果m == 0,说明nums2还有元素未遍历到，继续遍历nums2;
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }
        int index = m + n -1;
        while(m > 0 || n > 0){
            if(n - 1 < 0){
                break;
            }else if(m - 1 < 0){
                nums1[index] = nums2[n - 1];
                n --;
            }else{
                if(nums1[m - 1] > nums2[n - 1]){
                    int num = nums1[index];
                    nums1[index] = nums1[m -1];
                    nums1[m -1] = num;
                    m --;
                }else{
                    nums1[index] = nums2[n -1];
                    n --;
                }
            }
            index --;
        }

    }

    public static void main(String[] args) {
        int [] nums1 = new int[]{0,0};
        int [] nums2 = new int[]{1};
        EightyEight e = new EightyEight();
        e.merge2(nums1, 0, nums2, 1);
        System.out.println(Arrays.toString(nums1));
     }
}
